// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 使用滚动数组进行优化：删除横坐标，从右往左填表

// 例题 1:
// 描述
//        你有一个背包，最多能容纳的体积是V。
//
//        现在有n个物品，第i个物品的体积为 v[i],价值为 w[i]。
//
//        （1）求这个背包至多能装多大价值的物品？
//        （2）若背包恰好装满，求至多能装多大价值的物品？
//        输入描述：
//        第一行两个整数n和V，表示物品个数和背包体积。
//        接下来n行，每行两个数 v[i] 和 w[i]，表示第i个物品的体积和价值。
//
//        1 <= n, V, v[i], w[i] <= 1000
//
//        输出描述：
//        输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
//
//        示例1
//        输入：
//        3 5
//        2 10
//        4 5
//        1 4
//
//        输出：
//        14
//        9
//
//        说明：
//        装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。
//
//        示例2
//        输入：
//        3 8
//        12 6
//        11 8
//        6 8
//
//        输出：
//        8
//        0
//
//        说明：
//        装第三个物品时总价值最大但是不满，装满背包无解。
//        备注： 要求O(nV)的时间复杂度，O(V)空间复杂度

// 解题思路:
// 01 背包模板题：
// dp1[i][j] 表示从 [0, i] 件物品中选择，体积不超过 j 的最大价值
// 根据最后一个物品的选择分类讨论：
// 如果 v[i] <= j, 可以选 i 物品：dp1[i][j] = dp1[i - 1][j - v[i]] + w[i]
// 不选 i 物品：dp1[i][j] = dp1[i - 1][j]

// dp2[i][j] 表示从 [0, i] 件物品中选择，体积等于 j 的最大价值
// 初始化：
// dp2[0][j] (1 <= j <= V): 全部初始化为 -1, 表示不能凑出体积恰好为 j 的物品
// 根据最后一个物品的选择分类讨论：
// 如果 v[i] <= j && dp2[i - 1][j - v[i]] != -1, 可以选 i 物品：dp2[i][j] = dp2[i - 1][j - v[i]] + w[i]
// 不选 i 物品：dp2[i][j] = dp2[i - 1][j]
// 返回值：
// 如果 dp2[n][V] == -1，表示凑不出来 V 体积的物品，返回 0
// 否则直接返回 dp2[n][V]

import java.util.Scanner;

public class Knapsack01 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int V = in.nextInt();
            int[] v = new int[n + 1];
            int[] w = new int[n + 1];

            for(int i = 1; i <= n; i++){
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }
            int[][] dp = new int[n + 1][V + 1];
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= V; j++){
                    if(v[i] <= j){
                        dp[i][j] = dp[i - 1][j - v[i]] + w[i];
                    }
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
            }
            System.out.println(dp[n][V]);

            int[][] dp2 = new int[n + 1][V + 1];
            for(int j = 1; j <= V; j++){
                dp2[0][j] = -1;
            }
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= V; j++){
                    dp2[i][j] = dp2[i - 1][j];
                    if(v[i] <= j && dp2[i - 1][j - v[i]] != -1){
                        dp2[i][j] = Math.max(dp2[i][j], dp2[i - 1][j - v[i]] + w[i]);
                    }
                }
            }
            if(dp2[n][V] == -1) dp2[n][V] = 0;
            System.out.println(dp2[n][V]);
        }
    }
}
